Pedestrian1's BLOG
0%

P5293 [HNOI2019]白兔之舞

发表于 更新于

设为白兔跳了次终点为的方案数

可以用矩阵优化，则跳次可以用矩阵表示为,为行向量，初始只有第列为1，为输入矩阵

设，那么最终在第个点结束的答案为，即行向量的第列

接下来求方案数 单位根反演

令 可通过矩阵预处理得出，为次单位根，可通过求原根之后求出

算法变换

差卷积即可 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
ll get_r()
{
    vector<int> vec;
    ll now = mod - 1;
    for (int i = 2; i * i <= now; i++)
    {
        if (now % i)continue;
        vec.emplace_back(i);
        while (now % i == 0)now /= i;
    }
    for (int g = 2;; g++)
    {
        bool flag = true;
        for (auto p:vec)
            if (fpow(g, (mod - 1) / p) == 1)
            {
                flag = false;
                break;
            }
        if (flag)return g;
    }
}

ll wk[N];

int main()
{
    ll p, q, u, v, x, y, z, T;
    ll L;
    cin >> n >> k >> L >> x >> y >> mod;
    matrix Z;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%lld", &Z.a[i][j]);
    ll r = get_r();
    ll w = fpow(r, (mod - 1) / k);
    wk[0] = 1;
    for (int i = 1; i < k; i++)
        wk[i] = wk[i - 1] * w % mod;

    poly h(k);
    for (int i = 0; i < k; i++)
    {
        matrix f;
        f.a[1][x] = 1;
        f = f * (Z * wk[i] + matrix::E()).fpow(L);
        h[i] = f.a[1][y];
    }
    poly F(2 * k - 1), G(k);
    for (int i = 0; i < k; i++)
        G[i] = h[i] * fpow(w, 1ll * i * (i - 1) / 2) % mod;
    for (int i = 0; i < 2 * k - 1; i++)
        F[i] = fpow(fpow(w, mod - 2), 1ll * i * (i - 1) / 2);
    F = F * G.rev();
    const ll invk = fpow(k, mod - 2);
    for (int i = 0; i < k; i++)
        printf("%lld\n", fpow(w, 1ll * i * (i - 1) / 2) * invk % mod * F[k - 1 + i] % mod);
    return 0;
}